<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>150.逆波兰表达式求值</title>
</head>

<body>
    <div>
        <span id="org"></span>
        <br><br>
        <span id="expression"></span>
        <span id="result"></span>
    </div>
    <script>
        let tokens = ["4", "13", "5", "/", "+"]
            // let tokens = ["2", "1", "+", "3", "*"]
            // let tokens = ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
        let resultEle = document.getElementById("result")
        let ExpEle = document.getElementById("expression")
        let orgEle = document.getElementById("org")
        orgEle.innerHTML = `tokens = [${tokens}]`
            // 定义栈
        let stack = {
            datas: [],
            exp: [],
            //入栈
            Push: function(value) {
                this.datas.push(value)
            },
            //出栈，返回出栈值
            Pop: function() {
                return this.datas.pop()
            },
            //向数组末尾插入元素
            PushExp: function(value) {
                this.exp.push(value)
            },
            //向数组头部插入元素
            UnshiftExp: function(value) {
                this.exp.unshift(value)
            }
        }
        window.addEventListener('load', function() {
            //遍历tokens
            let insertEnd = true
            tokens.forEach(items => {
                //若当前元素不为number
                if (!isNaN(+items)) {
                    // 若为number，则入栈
                    stack.Push(+items)
                    insertEnd = true
                } else {
                    let y = stack.Pop()
                    let x = stack.Pop()
                        // 则出栈两位整数参与运算后入栈
                    computeExp(y, x, items, insertEnd)
                    stack.Push(compute(y, x, items))
                    insertEnd = false
                }
            });
            //运算完成后结果必定为栈底元素
            ExpEle.innerHTML = `${stack.exp.join(' ')} =`
            resultEle.innerHTML = stack.datas[0]
        })
        let compute = function(y, x, type) {
            // 因出栈顺序故交换参数位置
            switch (type) {
                case '*':
                    return x * y
                case '+':
                    return x + y
                case '-':
                    return x - y
                case '/':
                    return parseInt(x / y)
                default:
                    break
            }
        }
        let computeExp = function(y, x, type, insertS) {
            if (stack.exp.length === 0) {
                stack.PushExp(x)
                stack.PushExp(type)
                stack.PushExp(y)
                return
            }
            if (insertS) {
                stack.UnshiftExp('(')
                stack.PushExp(')')
                stack.PushExp(type)
                stack.PushExp(y)
            } else {
                stack.UnshiftExp('(')
                stack.PushExp(')')
                stack.UnshiftExp(type)
                stack.UnshiftExp(x)
            }
        }
    </script>
</body>

</html>